A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Packet-based computer networks increasingly utilize label switching protocols for traffic engineering and other purposes. Multi-Protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks. MPLS may be viewed as a protocol that allows packet-based networks to emulate certain properties of a circuit-switched network. By utilizing MPLS, a source device can request a path through a network to a destination device, i.e., a Label Switched Path (LSP). An LSP defines a distinct path through the network to carry MPLS packets from the source device to a destination device. Each router along an LSP allocates a label and propagates the label to the closest upstream router along the path for use in forwarding MPLS packets along the path. Routers along the path cooperatively perform MPLS operations to forward the MPLS packets along the established path.
Routers at the beginning of the LSP are commonly known as ingress routers, while routers at the end of the LSP are commonly known as egress routers. Ingress and egress routers are more generally referred to as label edge routers (LERs). Internal routers along the LSP are commonly referred to as label switch routers (LSRs). A set of packets to be forwarded along the LSP is referred to as a forwarding equivalence class (FEC). A FEC, for example, may specify any packets associated with a particular destination address or prefix. As another example, the FEC may define quality of service (QoS) characteristics for the set of packets. A plurality of FECs may exist for each LSP, but there may be only one LSP for any given FEC. The ingress LER uses routing information, propagated from the egress LER, to determine the LSP, to assign labels for the LSP, and to affix a label to each packet of the FEC. The LSRs utilize MPLS protocols to receive MPLS label mappings from downstream LSRs and to advertise MPLS label mappings to upstream LSRs. When an LSR receives an MPLS packet from an upstream router, it switches the MPLS label according to the information in its forwarding table and forwards the packet to the appropriate downstream LSR or LER. The next router along the LSP is commonly referred to as a downstream router or a next hop. The egress LER removes the label from the packet and forwards the packet to its destination in accordance with standard routing protocols.
Each LSR within the MPLS network maintains a separate and distinct label space from every other LSR within the MPLS network, and each LSR along a given LSP may assign a different MPLS label to the same FEC associated with the LSP. As a result of the distinct label spaces and random mappings, one or more LSRs may assign different labels to a FEC associated with packets to be forwarded to a given destination IP address or prefix. Thus, when establishing a LSP through a network, the LSRs exchange label mappings to overcome the random and independent assignment of MPLS labels to different FECs.
In this way, each router along the LSP maintains a context that associates a FEC with an incoming label and an outgoing label. When an LSR receives a labeled packet, the LSR typically swap the label (i.e., the incoming label) with the outgoing label by performing a exact match label lookup in its internal context. The LSR then performs a full label swap to replace at least one of the labels in the packet with a label allocated by the next hop LSR. The LSR then forwards the packet to the next LSR along the LSP.